#include <vector>
#include <string>
using namespace std;
class Solution {
public:
    //dfs
    vector<vector<string>> ans;
    vector<string> now;
    int n;
    bool can_col(int row, int col)
    {
        for(int i = 0; i < row; ++i)
            if(now[i][col] == 'Q') return false;
        return true;
    }

    bool can_xie(int row, int col)
    {
        //cout << "xie:" << row << ' ' << endl;
        int tmp_row = row, tmp_col = col;
        while(row-- && col--)
            if(now[row][col] == 'Q') return false;
        row = tmp_row, col = tmp_col;
        while(row-- > 0 && col++ < n - 1)
            if(now[row][col] == 'Q') return false;
        return true;
    }

    void dfs(int u, int n)
    {
        //cout << u << endl;
        if(u == n) ans.push_back(now);
        string tmp(n, '.');
        //枚举每列判断可能性
        for(int i = 0; i < n; ++i)
            if(can_col(u, i) && can_xie(u, i))
            {
                //cout << "---" << i << endl;
                tmp[i] = 'Q';
                now.push_back(tmp);
                dfs(u + 1, n);
                tmp[i] = '.';
                now.pop_back();
            }
    }
    vector<vector<string>> solveNQueens(int _n) {
        n = _n;
        dfs(0, n);
        return ans;
    }
};